package main.面试金典第六版;

import java.util.Arrays;

public class Interview05 {
    public static void main(String[] args) {
        System.out.println("面试题05.01：插入");
        System.out.println("面试题05.02：二进制数转字符串");
        System.out.println("面试题05.03：翻转数位");
        System.out.println("面试题05.04：下一个数");
        System.out.println("面试题05.06：整数转换");
        System.out.println("面试题05.07：配对交换");
        System.out.println("面试题05.08：绘制直线");
    }
}

class Interview_05_01{
    public int insertBits(int N, int M, int i, int j) {
        int left = N>>j>>1; //把最左边的部分调整好了，即抛弃了替换部分和低位部分
        left = left<<j<<1;  //因此最后要进行或运算，所以把他再移到原来的高位上。
        int middle = M<<i;  //替换N的j<-----i位，那么只需要将M左移i位即可
        int right = N&((1<<i)-1);//只需要N的低位，将高位置零,(1<<2)-1 = (11)2
        return left | middle | right;
    }
}

class Interview_05_02{
    public String printBin(double num) {
        StringBuffer str=new StringBuffer("0.");
        int i=0;
        while (num!=0&&i<6) {
            double result=num*2;
            str.append((int) result);
            num=result>=1 ? result-1 : result;
            i++;
        }
        return num==0? str.toString() : "ERROR";
    }
}

class Interview_05_03{
    public int reverseBits(int num) {
        int cur = 0;
        int insert = 0;
        int res = 1;
        for(int i = 0; i < 32; i++){
            if((num & (1 << i)) != 0){
                cur += 1;
                insert += 1;
            }else{
                insert = cur + 1;
                cur = 0;
            }
            res = Math.max(res , insert);
        }
        return res;
    }
}

class Interview_05_04{
    public int[] findClosedNumbers(int num) {
        if(num==Integer.MAX_VALUE) return new int[]{-1,-1};
        int[] ans=new int[2];
        ans[0]=getBig(num);
        ans[1]=getSmall(num);
        return ans;
    }

    public int getBig(int num){
        int cnt=0;
        if((num&(1<<cnt))==0){//去掉低位开始的0
            while(cnt<31&&(num&(1<<cnt))==0) cnt++;
        }
        int c1=cnt;//此时cnt为从低位往高位数第一个1的位置
        while(cnt<31&&(num&(1<<cnt))>0) cnt++;
        if(cnt==31) return -1;
        num+=(1<<cnt);//    ...00111000
        cnt--;
        num-=(1<<cnt);//变为   01011000
        cnt--;
        int count=0;
        while(c1>0&&cnt>0&&( num&(1<<cnt) )>0){//c1大于0才需要右移动
            num-=(1<<cnt);
            count++;
            cnt--;
        }
        while(count>0){
            count--;
            num+=(1<<count);
        }
        return num;
    }

    public int getSmall(int num){
        int cnt=0;
        if((num&(1<<cnt))>0){//去掉开始的1
            while(cnt<31&& (num & (1<<cnt))>0) cnt++;
        }
        int c0=cnt;//此时cnt为从低位到高位第一个0的位置
        while(cnt<31&&(num&(1<<cnt))==0) cnt++;
        if(cnt==31) return -1;
        num-=(1<<cnt);
        cnt--;
        num+=(1<<(cnt));//1000111-》0100111
        int cha=cnt-c0;//cnt指向从低位到高位第一个一串0后面的1 cha="差"是要左移的位数
        while(cnt-c0>0){
            cnt--;
            num+=(1<<cnt);
        }
        while(cha>0){//把最右边清0
            cha--;
            num-=(1<<cha);
        }
        return num;
    }
}

class Interview_05_06{
    public int convertInteger(int A, int B) {
        char[] strA=new char[32],strB=new char[32];
        Arrays.fill(strA,'0');
        Arrays.fill(strB,'0');
        char[] a=Integer.toBinaryString(A).toCharArray(),b=Integer.toBinaryString(B).toCharArray();
        for (int i=0;i<a.length;i++){
            strA[31-i]=a[a.length-1-i];
        }
        for (int i=0;i<b.length;i++){
            strB[31-i]=b[b.length-1-i];
        }
        int count=0;
        for (int i=0;i<32;i++) {
            if (strA[i]!=strB[i]) count++;
        }
        return count;
    }
}

class Interview_05_07{
    public int exchangeBits(int num) {
        int result = 0;
        for (int i = 0; i < 32; i+= 2) {
            result += (((num&(1<<i))*2) + ((num& (1<<(i + 1)))/2));
        }
        return result;
    }
}

class Interview_05_08{
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        StringBuilder sb = new StringBuilder();
        int start = y * w + x1, end = y * w + x2;
        for(int i = 0;i < 32 * length; ++i){
            if(sb.length() >= start && sb.length() <= end) sb.append('1');
            else sb.append('0');
        }
        int[] result = new int[length];
        for(int i = 0;i < length; ++i){// 以32位为单位截取字符串转化为无符号整型。
            result[i] = Integer.parseUnsignedInt(sb.substring(i * 32, i * 32 + 32), 2);
        }
        return result;
    }
}